#ifndef GAMEENGINE_CORE_GRAPH_HPP
#define GAMEENGINE_CORE_GRAPH_HPP

#ifdef GAMEENGINE_NAMESPACES
namespace GameEngine {
#endif

#ifndef DOXYGEN_IGNORE
//! No links set
template <class N, class L>
typename Graph<N,L>::LinkSet Graph<N,L>::no_links_ = Graph<N,L>::LinkSet();
#endif


//! Default constructor
template <class N, class L>
Graph<N,L>::Graph() {}

//! Copy constructor
/*!
 @param rhs The graph to copy
 @note This function is slow and should be avoided if possible
 */
template <class N, class L>
Graph<N,L>::Graph(const Graph& rhs) {
	// Iterate over the nodes
	nodes_.clear();
	foreach ( N node, rhs.nodes_ ) {
		add_node(node);
	}

	// Iterate over the links
	links_.clear();
	map_.clear();
	foreach ( L link, rhs.links_ ) {
		// Get the link nodes in the list
		N_pointer node1 = find_node(*link.node1());
		N_pointer node2 = find_node(*link.node2());

		// Add the link
		add_link(L(link.value(),node1, node2));
	}
}

//! Destructor
template <class N, class L>
Graph<N,L>::~Graph() {}

//! Assignment operator
/*!
 @param rhs The graph to copy
 @note This function is slow and should be avoided if possible
 */
template <class N, class L>
Graph<N,L>& Graph<N,L>::operator=(const Graph& rhs) {
	// Iterate over the nodes
	nodes_.clear();
	foreach ( N node, rhs.nodes_ ) {
		add_node(node);
	}

	// Iterate over the links
	links_.clear();
	foreach ( L link, rhs.links_ ) {
		// Get the link nodes in the list
		N_pointer node1 = find_node(*link.node1());
		N_pointer node2 = find_node(*link.node2());

		// Add the link
		add_link(L(link.value(),node1, node2));
	}
	return *this;
}

//! List of nodes in the graph
/*!
 @return A constant reference to the list of nodes of the graph
 */
template <class N, class L>
const std::set< N >& Graph<N,L>::nodes() const {
	return nodes_;
}

//! List of links in the graph
/*!
 @return A constant reference to the list of links of the graph
 */
template <class N, class L>
const std::set< L >& Graph<N,L>::links() const {
	return links_;
}

//! List of links associated to the given graph node
/*!
 @param node A pointer to the node
 @return A constant reference to the list of links associated to the given graph node
 @note If node does not belong to the graph, or if there is no link heading to that
       node, then returned list is empty
 */
template <class N, class L>
const typename Graph<N,L>::LinkSet& Graph<N,L>::links(N_pointer_const node) const {
	QMap< N_pointer_const, LinkSet >::const_iterator it = map_.constFind(node);
	if ( it == map_.end() ) return no_links_;
	return it.value();
}

//! Add the node to the list of nodes
/*!
 @param node The node to add to the graph
 */
template <class N, class L>
typename Graph<N,L>::N_pointer Graph<N,L>::add_node(const N& node) {
	std::pair< std::set< N >::iterator, bool > pair = nodes_.insert(node);
	if ( pair.second == false ) return nil;
	return &(*pair.first);
}

//! Find the node in the list of nodes
/*!
 @param node The node to find in the graph
 */
template <class N, class L>
typename Graph<N,L>::N_pointer_const Graph<N,L>::find_node(const N& node) const {
	std::set< N >::const_iterator it = nodes_.find(node);
	if ( it == nodes_.end() ) return nil;
	return &(*it);
}

//! Find the node in the list of nodes
/*!
 @param node The node to find in the graph
 */
template <class N, class L>
typename Graph<N,L>::N_pointer Graph<N,L>::find_node(const N& node) {
	std::set< N >::iterator it = nodes_.find(node);
	if ( it == nodes_.end() ) return nil;
	return &(*it);
}

//! Remove the node from the list of nodes
/*!
 @param node The node to remove from the graph
 @param remove_links If set to true, also removes all links associated to the node
 */
template <class N, class L>
bool Graph<N,L>::remove_node(const N& node, bool remove_links) {
	// If links should not be checked, there is not much to do
	if ( !remove_links ) return nodes_.remove(node);

	// Get the node pointer in the set of nodes
	bool res = remove_links(node);
	return res && nodes_.remove(node);
}

//! Add the link to the list of links
/*!
 @param link The link to add to the graph
 @note The nodes must exist in the graph prior to the link insertion
 */
template <class N, class L>
typename Graph<N,L>::L_pointer Graph<N,L>::add_link(const L& link) {
	// Check nodes
	N_pointer n1 = nil;
	N_pointer n2 = nil;

	// First node
	{{
		N_pointer_const node1 = dynamic_cast<N_pointer_const>(link.node1());
		if ( node1 == nil ) return nil;
		n1 = find_node(*node1);
		if ( n1 == nil ) return nil;
	}}

	// Second node
	{{
		N_pointer_const node2 = dynamic_cast<N_pointer_const>(link.node2());
		if ( node2 == nil ) return nil;
		n2 = find_node(*node2);
		if ( n2 == nil ) return nil;
	}}

	// Add the link
	std::pair< std::set< L >::iterator, bool > pair = links_.insert(link);
	if ( pair.second == false ) return nil;
	L_pointer res = &(*pair.first);

	// Reference the link
	QMap< N_pointer_const, LinkSet >::iterator it = map_.find(n1);
	if ( it == map_.end() ) {
		LinkSet set; set.insert(res);
		map_.insert(n1,set);
	}
	else {
		it->insert(res);
	}
	it = map_.find(n2);
	if ( it == map_.end() ) {
		LinkSet set; set.insert(res);
		map_.insert(n2,set);
	}
	else {
		it->insert(res);
	}

	// Return link
	return res;
}

//! Find the link in the list of links
/*!
 @param link The link to find in the graph
 */
template <class N, class L>
typename Graph<N,L>::L_pointer_const Graph<N,L>::find_link(const L& link) const {
	std::set< L >::iterator it = links_.find(link);
	if ( it == links_.end() ) return nil;
	return &(*it);
}

//! Find the link in the list of links
/*!
 @param link The link to find in the graph
 */
template <class N, class L>
typename Graph<N,L>::L_pointer Graph<N,L>::find_link(const L& link) {
	std::set< L >::iterator it = links_.find(link);
	if ( it == links_.end() ) return nil;
	return &(*it);
}

//! Remove the link from the list of links
/*!
 @param link The link to remove from the graph
 */
template <class N, class L>
bool Graph<N,L>::remove_link(const L& link) {
	// Get link in link list
	L_pointer l = find_link(link);

	// Dereference link
	QMap< N_pointer_const, LinkSet >::iterator it = map_.find(link.node1());
	if ( it != map_.end() ) it->erase(l);
	it = map_.find(link.node2());
	if ( it != map_.end() ) it->erase(l);

	// Erase link
	return ( links_.erase(link) > 0 );
}

//! Remove all links referencing the given node from the list of links
template <class N, class L>
bool Graph<N,L>::remove_links(const N& node) {
	// Find the node in the list
	N_pointer n = find_node(node);
	if ( n == nil ) return false;

	// Iterate over the links
	bool res = false;
	foreach ( L link, links_ ) {
		// Check if link should be removed
		bool to_remove = false;
		if ( link.node1() == n ) to_remove = true;
		else if ( link.node2() == n ) to_remove = true;

		// Remove link
		if ( to_remove ) res |= remove_link(link);
	}

	// Return status
	return res;
}

#ifdef GAMEENGINE_NAMESPACES
} // namespace GameEngine
#endif

#endif
